package leetcode.dp;

import java.util.Scanner;

/**
 * leetCode 5
 * 最小编辑距离
 * 给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数
 * 思路：dp[i][j] 表示word1 的前i和word2 的前j 的最小编辑距离，则
 * if(word1[i] == word2[j]) dp[i][j] = dp[i-1][j-1]
 * else dp[i][j] = min(dp[i-1][j-1] + 1, dp[i - 1][j] + 1, dp[i][j - 1] + 1)
 * 注意 dp[i][j] = min(dp[i-1][j-1] + 1 .. 而不是 + 2，它只表示第i和第j个字符要怎么动，想着要先加一个字符再改是错误的

 */
public class Dp72 {

    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        //利用hasNextXXX()判断是否还有下一输入项
        while (sc.hasNext()) {
            //利用nextXXX()方法输出内容
            String str = sc.next();
            new Dp72().minDistance(str.split(",")[0], str.split(",")[1]);
        }
    }
    public int minDistance(String word1, String word2) {
        int [][] dp = new int[word1.length() + 1][word2.length() + 1];
        // 子串长度为1和为2的初始化
        for(int i = 0; i <= word1.length(); i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= word2.length(); j++){
            dp[0][j] = j;
        }
        for(int i = 1; i <= word1.length(); i++){
            for(int j = 1 ;j <= word2.length();j ++){
                // i,j 表示第几个字符
                if(word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = Math.min(dp[i-1][j-1] + 1, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
            }
        }
        return dp[word1.length()][word2.length()];
    }
}
